Many hardware designs, such as bus protocols, coherent fabrics, memory sub-systems, and arithmetic datapaths, can have multiple (sometimes hundreds or thousands of) transactions “in-flight” at any point in time. Such hardware designs are referred to as multi-transactional hardware designs. A transaction is an exchange or interaction of data between start and end points of the design. A transaction is “in-flight” if it has been accepted for processing at an input interface of a component of the design (e.g. a cache) and has not been issued out on an output interface of that component. Accordingly, when a transaction first appears on an input interface of a component it becomes in-flight and it remains in-flight until the transaction is issued out on an output interface of the component.
Often multiple in-flight transactions need to access the same resource, such as a cache, arbiter, memory etc. which can create hazards. A hazard is a condition that occurs when more than one transaction (originating from the same or different requestors) tries to gain access to a shared resource (e.g. memory) at the same time. For example, if there is a write transaction and a read transaction to the same memory address, if the write is issued before the read then the expected behavior is that the write should be completed before the read so that the read will get the new value written by the write. If, however, the read is completed before the write then the read will get the old value instead of the new value resulting in a hazard.
To eliminate hazards the hardware may be designed to implement an ordering on the transactions. This typically involves assigning to the transactions a unique identifier and using a hardware data structure to track the transactions and enforce an order using the unique identifiers. For example, the hardware data structure may ensure that when transaction requests (e.g. read/write requests) are issued on an interface then the corresponding responses (e.g. data payloads) come back in the same order in which the transaction requests were issued.
In some cases ordering does not need to be absolutely enforced (e.g. not all transactions issued to a slave (e.g. memory or cache) have to be completed in the same order in which they were issued). For example, a design with multiple requestors (e.g. multiple masters) issuing transaction requests to a single resource (e.g. slave) can have several hundred or thousand transactions in-flight at any point in time. It may not be necessary for all the transactions issued to the slave to be completed in the order they were issued but only for the transactions issued from each requestor to be completed in order.
This type of ordering is typically implemented by a data structure that comprises a FIFO (First In First Out) for each requestor to keep track of the transactions for that requestor. The data structure also comprises a register set/clear mechanism that is used to enable transaction responses to come back out of order with respect to transaction requests from other masters. Each FIFO may use a two-dimensional array and multiple pointers (e.g. a read pointer and a write pointer) to keep track of elements in the array. However, formal verification using a FIFO for tracking ordered transactions can make the formal verification difficult.
The embodiments described below are provided by way of example only and are not limiting of implementations which solve any or all of the disadvantages of known data structures for tracking ordered transactions.